package puzzle.projecteuler.p200;

import java.math.BigInteger;
import java.util.Arrays;

public class Problem104A {

	/**
	 * 1. check the last 9 digits will be easy
	 * 2. when we get a f_k, whose last 9 digits are 1-9 pandigital, then check its first 9 digits
	 * 3. 
	 * @param args
	 */
	public static void main(String[] args) {

		long f1 = 1L;
		long f2 = 1L;
		long x = 0L;
		String a = null;
		
		int n = 1;
		while (true) {
			x = f1;
			f1 = f2;
			f2 = (x + f2)%1000000000;
			a = String.valueOf(f1);
			if (a.length() < 9) {
				n ++;
				continue;
			} else {
				if (check(a)) {
					System.out.println(n+1);
					BigInteger t = f(n+1);
					String b = t.toString();
					String s = b.substring(0, 9);
					if (check(s)) {
						System.out.println(n+1);
						break;
					}
				}
				n ++;
				continue;
			}
		}
		System.out.println(n+1);
	}
	
	public static boolean check(String s) {
		if (s.length() == 9) {
			char[] c = s.toCharArray();
			Arrays.sort(c);
			String ns = "";
			for (int i = 0; i < 9; i ++) {
				ns += c[i];
			}
			return ("123456789".equalsIgnoreCase(ns));
		} else {
			return false;
		}
	}

	/*
	 * In order to use less memories 
	 */
	private static BigInteger F1 = BigInteger.ONE;
	private static BigInteger F2 = BigInteger.ONE;
	private static int F_start = 2;
	
	public static BigInteger f(int n) {

		while (F_start < n) {
			BigInteger x = F1;
			F1 = F2;
			F2 = x.add(F2);
			F_start ++;
		}
		return F2;
	}
	
}
